package com.qch.edu.sort.gaojiSort;

/**
 * @Author qch
 * @Date 2021/3/6
 * 希尔排序（改进的插入排序）：不稳（跳着排） ，O（n^1.3）,空间O(1)
 * 定义一个间隔 group=4,一组按插入排序排好数据
 * 然后以间隔group=2排序
 * 最后间隔group=1排序
 * 间隔大的时候n挪的次数比较小，间隔小的时候挪的距离短
 *
 * Knuth序列
 * h=1
 * h=3*h+1
 */
public class XierSort {
    public static void main(String[] args) {
        int arr[]={10,9,2,4,5,1,3,8,6,55};
        //int arr[]={10};
        sort(arr);
        print(arr);
    }
    static void sort(int arr[]){
        int h=1;
        while (h<=arr.length/3)
        {
            h=h*3+1;
        }
        //int gap=4;
        //arr.length/2=arr.length>>1
        //for(int gap=arr.length>>1;gap>0;gap/=2) {} n/2
        for(int gap=h;gap>0;gap=(gap-1)/3) {
            //普通的插入排序
            for (int i = gap; i < arr.length; i++) {
                for (int j = i; j > gap - 1; j -= gap) {
                    if (arr[j] < arr[j - gap]) {
                        swap(arr, j, j - gap);
                    }
                }
            }
        }
    }
    static void swap(int[] arr,int i,int j)
    {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    static void print(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+",");
        }
    }
}
